Processors have a limited number of hardware registers to use when executing instructions. In cases where there are not enough registers to hold all program variables currently in use some of the variables used by the instructions may be “spilled” into memory to free registers. When a variable is spilled, a compiler creates spill code that is inserted into the low-level code created by the compiler to manage these spilled variables. Selecting how to spill variables depends on many different factors, including machine architecture, complexity of program, and compiler efficiency. For example, RISC machines generally have many more hardware registers as compared with CISC machines making efficient spill code much less important on the RISC machines.
Generally, the need for registers increases with the complexity of programs. This complexity, in turn, creates more spilled variables and low-level spill code. Memory operations, however, are generally significantly slower than register accesses causing the program instructions that include spill code to run slower. In order to help alleviate the register pressure created by an excess of variables over available registers, various register allocation methods have been developed to determine which variables to spill.
Some of these allocation methods are widely used in optimizing compilers. One such method is a graph-coloring register allocation method known as a Chaitin-style allocation method. Generally, the method constructs an interference graph for all variables used within a procedure. A color is then assigned to each available hardware register on the processor. For example, if seven hardware registers are available then seven distinct colors for coloring the graph are available. An attempt to color each node within the interference graph with a distinct color is then made. If the coloring fails, the method chooses a variable(s) from the graph to spill and spill code is generated for the spilled variables. This method is repeated until coloring of the nodes is successful.
While methods exist to allocate registers, they are not optimized for complex instruction set computing (CISC) two-address machines. Instead, the development of allocation methods has been directed to three-address reduced instruction set computing (RISC) machines.